package sort.memory;

/**
 * @author tuyou
 * @date 2020-11-04 23:56:06
 */
public class QuickSort {

    public static void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    public static void sort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        //以nums[start]为这轮排序的基准，这样也可以作为right向左遍历的监视器，不会越界
        int left = start;
        int right = end + 1;
        int base = nums[start];
        while (left < right) {
            //先移动右指针把左指针填了
            while (left < right && nums[--right] > base);
            nums[left] = nums[right];

            //再移动左指针填有指针留下的坑
            while (left < right && nums[++left] < base);
            nums[right] = nums[left];
        }
        //最后left==right
        nums[left] = base;

        //left一定大于等于左边，小于等于右边，所以不用参与排序
        sort(nums, start, left - 1);
        sort(nums, right + 1, end);
    }
}
